package 力扣_链表.双指针;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zx
 * @create 2022-08-15 15:30
 */
public class 环形链表II_142 {
    /**
     使用两个指针,fast与slow。它们起始都位于链表的头部。随后,slow指针每次向后移动一个位置，而 fast 指针向后移动两个位置。
     如果链表中存在环，则fast指针最终将再次与slow指针在环中相遇。如下图所示，设链表中环外部分的长度为a。slow指针进入环后，
     又走了b的距离与fast相遇。此时,fast 指针已经走完了环的n圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。
     根据题意，任意时刻,fast指针走过的距离都为slow指针的2倍。因此,推导出a=c+(n−1)(b+c)的等量关系,
     我们会发现:从相遇点到入环点的距离加上n−1圈的环长,恰好等于从链表头部到入环点的距离。
     因此，当发现slow与fast相遇时,我们再额外使用一个指针ptr。起始,它指向链表头部;
     随后,它和slow每次向后移动一个位置。最终，它们会在入环点相遇。
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow){
                ListNode pod = head;
                while(pod != slow){
                    pod = pod.next;
                    slow = slow.next;
                }
                return pod;//入环点相遇,返回入环点
            }
        }
        return null;
    }
}
